package slidingWindowAlgorithm.review4_19;

import slidingWindowAlgorithm.Class76;

import java.util.HashMap;

public class CLass76 {

    public String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<>();
        for (char c:t.toCharArray()
             ) {
            need.put(c,need.getOrDefault(c,0)+1);
        }
        HashMap<Character, Integer> window = new HashMap<>();
        int left=0,right=0;
        int valid=0;
        int size = s.length();
        int minLen=size+1;
        int start=0;
        while (right<size){
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if (window.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            int needSize = need.size();
            while (valid==needSize){
                 c= s.charAt(left);
                 left++;
                 if (need.containsKey(c)){
                     if (window.get(c).equals(need.get(c))){
                         valid--;
                         window.put(c,window.get(c)-1);
                     }
                     if (valid!=needSize){
                         if (right-left+1<minLen){
                             start=left-1;
                             minLen=right-left+1;
                         }

                     }
                 }
            }
        }

  return  minLen==size+1?"":s.substring(start,start+minLen);
    }

    public static void main(String[] args) {
        Class76 class76 = new Class76();
        System.out.println(class76.minWindow("abcdfg", "bcg"));
    }


}
